
/**
 * Sorted tree.
 * @param <T> Generic type.
 * @author Lukas Koell
 * @author David Medenjak
 * @author Johannes Riedmann
 */
public abstract class SortedTree<T extends Comparable<? super T>> extends Tree<T> {
    
    @Override
    /**
     * inserts a node so that the left subnodes are always
     * smaller than the right subnodes
     */
    public void add(T node) {
        Node<T> newNode = new Node<T>(node, null, null, null);
        if(getRoot() == null){
            setRoot(newNode);
            return;
        }

        Node<T>pos = getRoot();
        Node<T>parent = getRoot();
        boolean left = false;
        
        while(pos != null){
            if(newNode.getValue().compareTo(pos.getValue()) < 0){
                parent = pos;
                pos = pos.getLeftChild();
                left = true;
            }else{
                parent = pos;
                pos = pos.getRightChild();
                left = false;
            }
        }
        
        newNode.setParent(parent);
        if(left){
            parent.setLeftChild(newNode);
        }else{
            parent.setRightChild(newNode);
        }
        newNode.setLeftChild(null);
        newNode.setRightChild(null);
        
    }
    
    @Override
    /**
     * searches the tree in logarithmic time
     */
    public Iter<Boolean> search(T node) {
        Tree<Boolean> boolTree = new ReplaceableTree<Boolean>();
        Node<T> currentNode = getRoot();
        
        while(currentNode != null){
            // we found it!
            if(currentNode.getValue().compareTo(node) == 0){
                return boolTree.iterator();
            }
            if(currentNode.getValue().compareTo(node) > 0){
                // our searched item must be in left subtree
                currentNode = currentNode.getLeftChild();
                boolTree.add(false);
            }else if(currentNode.getValue().compareTo(node) < 0){
                // our searched item must be in right subtree
                currentNode = currentNode.getRightChild();
                boolTree.add(true);
            }
        }
         //nothing found, 
        return null;
    }
}
